Round Overview
Discuss this match
This problem set was pretty easy. Some coders completed their work in 20 minutes. There was a long list of contestants with a complete set of problems after 40 minutes and at the end of the challenge 86.15% of coders had submitted the hardest task. But only 36.18% of div1-hard solutions were correct. Im2Good, who made 12 successful challenges, won this match and became the Highest Match Total champion (a title that hasn’t changed since 05.08.01). misof and jdmetz took second and third.
In the division 2, korntest was first, followed by p45c4l and titid_gede who took second and third.
Used as: Division Two - Level One:
Value | 250 |
Submission Rate | 243 / 268 (90.67%) |
Success Rate | 209 / 243 (86.01%) |
High Score | a2nnu for 249.92 points (0 mins 30 secs) |
Average Score | 210.70 (for 209 correct submissions) |
The most elegant solution for this problem uses regular-expressions. Here is a sample Java submission:
1
2
3
4
for (int i = 0; i < numbers.length; i++)
numbers[i] = numbers[i].replaceAll(" ", "")
.replaceAll("[^0-9]", ".");
return numbers;
Used as: Division Two - Level Two:
Value | 400 |
Submission Rate | 223 / 268 (83.21%) |
Success Rate | 88 / 223 (39.46%) |
High Score | korntest for 390.85 points (4 mins 22 secs) |
Average Score | 297.17 (for 88 correct submissions) |
There are at most 19 split points. We can try all of them and choose one with the smallest A value (if any). Here is a sample Java submission:
1
2
3
4
5
6
7
for (int i = 1; i < conglutination.length(); i++) {
int A = strToInt(conglutination.substring(0, i));
int B = strToInt(conglutination.substring(i));
if (A >= 0 && B >= 0 && A + B == expectation)
return conglutination.substring(0, i) + "+" + conglutination.substring(i);
}
return "";
The only trick is that strToInt should return negative results for strings that represent integers greater than expectation.
Used as: Division Two - Level Three:
Value | 1000 |
Submission Rate | 162 / 268 (60.45%) |
Success Rate | 16 / 162 (9.88%) |
High Score | DarkSolver for 859.35 points (11 mins 54 secs) |
Average Score | 650.36 (for 16 correct submissions) |
Used as: Division One - Level Two:
Value | 500 |
Submission Rate | 226 / 231 (97.84%) |
Success Rate | 107 / 226 (47.35%) |
High Score | misof for 484.94 points (5 mins 2 secs) |
Average Score | 391.96 (for 107 correct submissions) |
There are only 1000 different buttons and we can test all of them. If we know the digits on the button how many clicks are required for typing the sequence? The secret is easy: if the next three digits in the sequence equals to the corresponding button’s digits, we should click three-digit button. The result will be optimal. Here is a sample Java submission:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//merge sequence into char array s
...
String ans = "";
int bestRes = s.length + 1;
for (char ch1 = '0'; ch1 <= '9'; ch1++)
for (char ch2 = '0'; ch2 <= '9'; ch2++)
for (char ch3 = '0'; ch3 <= '9'; ch3++) {
int curRes = 0;
int index = 0;
while (index < s.length) {
if (index + 2 < s.length && s[index] == ch1 &&
s[index + 1] == ch2 && s[index + 2] == ch3) {
index += 3;
} else {
index += 1;
}
curRes += 1;
}
if (curRes < bestRes) {
bestRes = curRes;
ans = "" + ch1 + ch2 + ch3;
}
}
return ans;
Some coders (for example Im2Good, John Dethridge…) used dynamic programming to obtain the required amount of clicks. This solution is also correct.
Used as: Division One - Level One:
Value | 250 |
Submission Rate | 229 / 231 (99.13%) |
Success Rate | 191 / 229 (83.41%) |
High Score | Eryx for 248.37 points (2 mins 18 secs) |
Average Score | 206.90 (for 191 correct submissions) |
For solving this problem we should manually round the value of Î . Note contains several first Î value digits and this amount is enough for solving this problem. Here is a sample Java submission:
1
2
3
4
5
6
7
8
9
10
11
12
byte[] pi = "3.141592653589793238462643383279".getBytes();
if (pi[precision + 2] > '4')
pi[precision + 1]++;
int index = precision;
while (pi[index + 1] > '9') {
pi[index + 1] = (byte)
'0';
pi[index]++;
index--;
}
return new String(pi, 0, precision + 2);
Used as: Division One - Level Three:
Value | 1000 |
Submission Rate | 199 / 231 (86.15%) |
Success Rate | 72 / 199 (36.18%) |
High Score | Krzysan for 978.74 points (4 mins 12 secs) |
Average Score | 739.29 (for 72 correct submissions) |
There are at most 1000 possible denominators. We can try all of them. If we know a denominator B, a numerator A of the closest fraction can be easily found using the following formula:
1
A = round(B * sqrt(N))
After that we can compare the obtained fraction with the currently best fraction and update it if needed. Where is the trick? The trick in the phrase “we can compare obtained fraction with the currently best fraction” because we can’t do it in a usual way:
1 2
if (abs(A1 / B1 - sqrt(N)) < abs(A2 / B2 - sqrt(N))) ...
The standard double type does not provide the required precision.
So, let’s solve the following problem. There are two fractions A1/B1 and A2/B2. Which of them is closer to sqrt(N)? Let A2/B2 be greater than A1/B1. If A2/B2 less than sqrt(N) or A1/B1 greater than sqrt(N) when the closest fraction is obvious (A2/B2 in the first case, A1/B1 in the second). So we can assume that
1
A1 / B1 < sqrt(N) < A2 / B2.
In this case the fraction A1/B1 is closer to sqrt(N) if and only if
1
sqrt(N) - A1 / B1 < A2 / B2 - sqrt(N)
And after a number of manipulations:
1
4 * N * (B1 * B2) 2 < (A1 * B2 + A2 * B1) 2
All described calculation can be done within 64bit integers.
Some coders was searching for the closest fraction minimizing abs((A/B)2 - N) function. In the problem limitations this solution is also possible.